L2-024 部落

题目 L2-024 部落

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf= 0x3f3f3f3f;

priority_queue<int> pq;

multiset<int> s;

const int MAXN=1e4+10;

struct DSU{

	vector<int> parent;

	DSU(int n){

		parent.resize(n+1);

		for(int i=0;i<=n;i++)	parent[i]=i;

	}

	int find(int x){

		if(parent[x]!=x)	parent[x]=find(parent[x]);

		return parent[x];

	}

	void unite(int x,int y){

		int fx=find(x);

		int fy=find(y);

		if(fx!=fy){

			parent[fx]=fy;

		}

	}

	bool connected(int x,int y){

		return find(x)==find(y);

	}

};

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	DSU dsu(MAXN);

	int n;cin>>n;

	unordered_set<int> exist;

	while(n--){

		int k;cin>>k;

		vector<int> circle(k);

		for(int i=0;i<k;i++){

			cin>>circle[i];

			exist.insert(circle[i]);

		}

		for(int i=1;i<k;i++){

			dsu.unite(circle[0],circle[i]);

		}

	}

	int countP=exist.size(),countT=0;

	set<int> roots;

	for(auto p:exist){

		roots.insert(dsu.find(p));

	}

	countT=roots.size();

	cout<<countP<<" "<<countT<<endl;

	int q;cin>>q;

	while(q--){

		int a,b;cin>>a>>b;

		cout<<(dsu.connected(a,b)?"Y":"N")<<endl;

	}

	return 0;

}

同类题型

视频讲解

⬅️ L2-023 图着色问题 🏠 00-天梯赛 ➡️ L2-025 分而治之